print "---------New-Run---------------------------------------------------------------------------------------------------";


datatype rectangle = Rect of int * int * int * int

datatype quadTree = EmptyQuadTree
    | Qt of rectangle * rectangle list * rectangle list *
    quadTree * quadTree * quadTree * quadTree

    

(*
emptyQtree e
TYPE: rectangle -> quadTree
*)
fun emptyQtree e = Qt(e,[],[],EmptyQuadTree,EmptyQuadTree,EmptyQuadTree,EmptyQuadTree);

(*
inExtent q, r
TYPE: quadTree, rectangle -> bool
PRE:
*)
fun inExtent (Qt(Rect(l1,t1,r1,b1),_,_,_,_,_,_), Rect(l2,t2,r2,b2)) =
    if (l2 >= l1) andalso (r2 <= r1) andalso (t2 <= t1) andalso (b2 >= b1) then
        true
    else
        false

(*
inVertical q, r
TYPE: quadTree, rectangle -> bool
PRE: r is in q:s extent
*)
fun inVertical (Qt(Rect(l1,t1,r1,b1),_,_,_,_,_,_), Rect(l2,t2,r2,b2)) =
    let
        val x = (l1+r1) div 2;
    in
        if (l2 < x) andalso (x < r2) then
            true
        else
            false
    end
    
(*
inHorizontal q, r
TYPE: quadTree, rectangle -> bool
PRE: r is in q:s extent
*)
fun inHorizontal (Qt(Rect(l1,t1,r1,b1),_,_,_,_,_,_), Rect(l2,t2,r2,b2)) =
    let
        val y = (t1+b1) div 2;
    in
        if (t2 > y) andalso (y > b2) then
            true
        else
            false
    end

(*
inTopLeft q, r
TYPE: quadTree, rectangle -> bool
PRE: r is in q:s extent
*)
fun inTopLeft (Qt(Rect(l1,t1,r1,b1),_,_,_,_,_,_), Rect(l2,t2,r2,b2)) =
    let
        val y = (t1+b1) div 2;
        val x = (l1+r1) div 2;
    in
        if (b2 >= y) andalso (r2 < x) then
            true
        else
            false
    end

(*
inTopRight q, r
TYPE: quadTree, rectangle -> bool
PRE: r is in q:s extent
*)
fun inTopRight (Qt(Rect(l1,t1,r1,b1),_,_,_,_,_,_), Rect(l2,t2,r2,b2)) =
    let
        val y = (t1+b1) div 2;
        val x = (l1+r1) div 2;
    in
        if (l2 >= x) andalso (b2 >= y) then
            true
        else
            false
    end

(*
inBottomRight q, r
TYPE: quadTree, rectangle -> bool
PRE: r is in q:s extent
*)
fun inBottomRight (Qt(Rect(l1,t1,r1,b1),_,_,_,_,_,_), Rect(l2,t2,r2,b2)) =
    let
        val y = (t1+b1) div 2;
        val x = (l1+r1) div 2;
    in
        if (l2 >= x) andalso (t2 < y) then
            true
        else
            false
    end

(*
inBottomLeft q, r
TYPE: quadTree, rectangle -> bool
PRE: r is in q:s extent
*)
fun inBottomLeft (Qt(Rect(l1,t1,r1,b1),_,_,_,_,_,_), Rect(l2,t2,r2,b2)) =
    let
        val y = (t1+b1) div 2;
        val x = (l1+r1) div 2;
    in
        if (r2 < x) andalso (t2 < y) then
            true
        else
            false
    end

(*
insertVertical q, r
TYPE: quadTree * rectangle -> quadTree
*)
fun insertVertical (Qt(extent,horizontal,vertical,topLeft,topRight,bottomLeft,bottomRight), r) =
    Qt(extent,horizontal,r::vertical,topLeft,topRight,bottomLeft,bottomRight);

(*
insertHorizontal q, r
TYPE: quadTree * rectangle -> quadTree
*)
fun insertHorizontal (Qt(extent,horizontal,vertical,topLeft,topRight,bottomLeft,bottomRight), r) =
    Qt(extent,r::horizontal,vertical,topLeft,topRight,bottomLeft,bottomRight);

(*
insertTopLeft q, r
TYPE: quadTree * rectangle -> quadTree
*)
fun insertTopLeft (Qt(extent,horizontal,vertical,topLeft,topRight,bottomLeft,bottomRight), r) =
    let
	val newTree = emptyQtree(r)
    in
	Qt(extent,horizontal,vertical,newTree,topRight,bottomLeft,bottomRight)
    end

(*
insertTopRight q, r
TYPE: quadTree * rectangle -> quadTree
*)
fun insertTopRight (Qt(extent,horizontal,vertical,topLeft,topRight,bottomLeft,bottomRight), r) =
    let
	val newTree = emptyQtree(r)
    in
	Qt(extent,horizontal,vertical,topLeft,newTree,bottomLeft,bottomRight)
    end

(*
insertBottomRight q, r
TYPE: quadTree * rectangle -> quadTree
*)
fun insertBottomRight (Qt(extent,horizontal,vertical,topLeft,topRight,bottomLeft,bottomRight), r) =
    let
	val newTree = emptyQtree(r)
    in
	Qt(extent,horizontal,vertical,topLeft,topRight,bottomLeft,newTree)
    end

(*
insertBottomLeft q, r
TYPE: quadTree * rectangle -> quadTree
*)
fun insertBottomLeft (Qt(extent,horizontal,vertical,topLeft,topRight,bottomLeft,bottomRight), r) =
    let
	val newTree = emptyQtree(r)
    in
	Qt(extent,horizontal,vertical,topLeft,topRight,newTree,bottomRight)
    end

(*
insert q, r
TYPE: quadTree * rectangle -> quadTree

- kolla om ligger i topleft, topright, bottomleft, bottomright
*)

fun insert (q : quadTree, r : rectangle) = 
    if inExtent (q, r) = true then
        if inVertical (q, r) = true then
            insertVertical (q, r)
	else if inHorizontal(q, r) = true then
	    insertHorizontal(q, r)
	else if inTopLeft(q, r) = true then
	    insertTopLeft(q, r)
	else if inTopRight(q, r) = true then
	    insertTopRight(q, r)
	else if inBottomRight(q, r) = true then
	    insertBottomRight(q, r)
	else if inBottomLeft(q, r) = true then
	    insertBottomLeft(q, r)
	else
	    q
    else
        q; (* Don't insert *)
        
val tree = emptyQtree(Rect(0,5,5,0));
val rectVE = Rect(1,3,3,1);
val rectHO = Rect(3,3,5,1);
val rectTL = Rect(0,4,1,3);
val rectTR = Rect(4,5,5,4);
val rectBL = Rect(0,1,1,0);
val rectBR = Rect(4,1,5,0);

insert(tree, rectVE);
print "_________________________VE______________";

insert(tree, rectHO);
print "_______________________Ho________________";

insert(tree, rectTL);
print "_____________________TL__________________";

insert(tree, rectTR);
print "___________________TR____________________";

insert(tree, rectBL);
print "_________________BL______________________";

insert(tree, rectBR);
print "_______________BR________________________";


(*
queryAux r, x, y
TYPE: rectangle * int * int -> bool
PRE: 
POST: true if coordinates (x, y) are within the rectangle r, otherwise false
*)
fun queryAux (Rect(l,t,r,b), x, y) =
    if (l <= x) andalso (x < r) andalso (b <= y) andalso (y < t) then
      true
    else
      false;

(*
query q, x, y
TYPE: quadTree * int * int -> rectangle list
PRE:
POST: generates a list of all rectangles in q that contains the coordinates (x, y)
*)
fun query(EmptyQuadTree, x, y) = []
  | query(Qt(_,horizontal,_,_,_,_,_), x, y) =
    if queryAux(hd horizontal) then
      (hd horizontal) :: []
    else
      ;
